package leetcode.D100.T31;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-08-10 16:57:11 星期二
 */

/**
 * 解法：
 * 分三步：
 * step1：找出后端是数组尾部的最长不上升子列，即从尾部开始查找一条最长不上升子列
 * step2：找出子列中比子列前一个元素大的最小元素，将它们交换位置
 * step3：将子列排序。由于子列本身就是一个不上升序列，所以排序很简单，直接整体反转即可
 *
 * 时间复杂度：O(n)，空间复杂度：O(1)
 */
public class Solution {
    // 一刷
    /*public void nextPermutation(int[] nums) {
        if(nums.length==1) {
            return;
        }
        int loc = nums.length-1;
        while(loc > 0) {
            if(nums[loc] > nums[loc-1]) {
                break;
            }
            --loc;
        }
        if(loc == 0) {
            reverse(nums, loc);
        } else {
            int target = nums.length-1;
            while(nums[target] <= nums[loc-1]) {
                --target;
            }
            int temp = nums[loc-1];
            nums[loc-1] = nums[target];
            nums[target] = temp;
            reverse(nums, loc);
        }
    }

    private void reverse(int[] nums, int loc) {
        int k = (nums.length-loc) / 2;
        for(int i=0; i<k; ++i) {
            int temp = nums[i+loc];
            nums[i+loc] = nums[nums.length-1-i];
            nums[nums.length-1-i] = temp;
        }
    }*/

    // 二刷
    public void nextPermutation(int[] nums) {
        int loc = nums.length-1;
        while (loc > 0) {
            if (nums[loc-1] < nums[loc])
                break;
            loc--;
        }
        if (loc == 0)
            reverse(nums, 0);
        else {
            int target = nums.length-1;
            while (nums[target] <= nums[loc-1])
                target--;
            swap(nums, loc-1, target);
            reverse(nums, loc);
        }
    }

    private void reverse(int[] nums, int start) {
        int left = start, right = nums.length-1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}
